package Euler348;

import java.util.*;
import ReusableCode.MathFunctions;

public class SumSquareCube {
	public static void main(String[] args) {
		//Get palindromes up to 999. million.
		List<Long> pals = MathFunctions.getPalindromes(99999);
		Map<Long, Long> squares = new HashMap<Long, Long>();
		Map<Long, Long> cubes = new HashMap<Long, Long>();
		long sum = 0;
		long palCount = 0;
		
		
		//Get a list of all cubes under 999 million.
		long maxCube = (long)Math.pow(999999999L, 1.0/3.0);
		for(int i = 1; i < maxCube;i++)
		{
			long cube = (long)Math.pow(i, 3.0);
			cubes.put((long)i, cube);
		}
		
		//Get a list of all cubes under 999 million.
		long maxSquare = (long)Math.pow(999999999L, 1.0/2.0);
		for(int i = 1; i < maxSquare;i++)
		{
			long square = (long)Math.pow(i, 2.0);
			squares.put(square,(long)i);
		}
		
		//For each palindrome, check if there are EXACTLY 4 square/cube sums that add up to it.
		for(int i = 0; i < pals.size() ; i++)
		{
			long pal = pals.get(i);
			int count = 0;
			
			for(int j = 1; j < cubes.size() ; j++)
			{
				long cube = cubes.get((long)j);
				long diff = pal-cube;
				
				if(count>4 || (diff<0))
				{
					break;
				}
				else
				{
					if(squares.containsKey((long)diff))
					{
						count++;
					}
				}
			}
			
			if(count==4)
			{
				sum += pal;
				palCount++;
				System.out.println(pal);
			}
			
			if(palCount==5)
			{
				break;
			}
		}
		
		System.out.println("Sum: " + sum);
		//System.out.println(squares);
		//System.out.println(cubes);
		//System.out.println(pals);
		//System.out.println(pals.size());
	}
	
	
	
}
